/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
    let stack = [root];

    while (stack.length > 0) {
        let len = stack.length,
            right = len - 1,
            left = 0;

        // 每次判断一层是否对称
        while (left <= right) {
            if (stack[left] === null && stack[right] === null) {
                left++
                right--
                continue
            }
            if (stack[left] === null || stack[right] === null) {
                return false
            }
            if (stack[left].val !== stack[right].val) {
                return false
            }
            left++
            right--
        }

        
        for (let i = 0; i < len; i++) {
            let node = stack.shift()
            node && stack.push(node.left)
            node && stack.push(node.right)
        }

    }
    return true;
};



/**
 * 递归
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
    return isSymmetricLevel(root.left,root.right)
};

// 1.确定递归参数和返回值
function isSymmetricLevel(left,right){
    // 2. 确定终止条件
    // 两方为null
    if(left === null && right === null){
        return true
    }
    // 一方为null  或者  两方都不为null且不相等
    if(left === null || right == null || left.val !== right.val){
        return false
    }
    // 3.确定递归逻辑
    // 两方都不为null且相等，往上判断
    return isSymmetricLevel(left.left,right.right) && isSymmetricLevel(left.right,right.left)
}